package gold.digger;

import gold.utils.InputUtil;
import gold.vo.TreeNode;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC108 {

    public TreeNode sortedArrayToBST(int[] arr) {
        return sortedArrayToBSTRecur(arr, 0, arr.length - 1);
    }

    public TreeNode sortedArrayToBSTRecur(int[] arr, int start, int end) {
        if (start > end) {
            return null;
        }

        int mid = start + (end - start) / 2;
        TreeNode root = new TreeNode(arr[mid]);
        root.left = sortedArrayToBSTRecur(arr, start, mid - 1);
        root.right = sortedArrayToBSTRecur(arr, mid + 1, end);
        return root;
    }

    public static void main(String[] args) {
        LC108 an = new LC108();
        int[] arr = InputUtil.toIntegerArray("[-10,-3,0,5,9]");
        System.out.println(an.sortedArrayToBST(arr));
    }
}
